\documentclass[a4paper,11pt]{article}


\usepackage{geometry}
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\usepackage[T1]{fontenc}
%\usepackage{tikz-uml}
\usepackage{relsize}
\usepackage{color}
\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{mauve}{rgb}{0.58,0,0.82}

\usepackage{listings}
\usepackage{float}
\usepackage{kpfonts}

\usepackage{graphicx}

\lstset{
language=C,
basicstyle=\footnotesize,
backgroundcolor=\color{white},
keywordstyle=\color{red},
commentstyle=\color{dkgreen},
stringstyle=\color{mauve},
numberstyle=\color{red},
morekeywords={string},
frame=BL,
aboveskip=1em,
belowskip=2em,
}
\lstset{
  literate={ù}{{\`u}}1
           {é}{{\'e}}1
           {è}{{\'e}}1
           {à}{{\`a}}1
}


\lstdefinelanguage{tikzuml}{language=[LaTeX]TeX, classoffset=0, morekeywords={umlbasiccomponent, umlprovidedinterface, umlrequiredinterface, umldelegateconnector, umlassemblyconnector, umlVHVassemblyconnector, umlHVHassemblyconnector, umlnote, umlusecase, umlactor, umlinherit, umlassoc, umlVHextend, umlinclude, umlstateinitial, umlbasicstate, umltrans, umlstatefinal, umlVHtrans, umlHVtrans, umldatabase, umlmulti, umlobject, umlfpart, umlcreatecall, umlclass, umlvirt, umlunicompo, umlimport, umlaggreg}, classoffset=1, morekeywords={umlcomponent, umlsystem, umlstate, umlseqdiag, umlcall, umlcallself, umlfragment, umlpackage}, classoffset=0,  sensitive=true, morecomment=[l]{\%}}

\geometry{margin=2.6cm}
\geometry{headheight=15pt}

\usepackage{fancyhdr}
\usepackage{fancyvrb}
\usepackage{float}
\usepackage[footnote,smaller]{acronym}

\pagestyle{fancy}
\rhead{IT202 - Projet de Système d'Exploitation}

%\acrodef{LABRI}{Laboratoire Bordelais de Recherche en Informatique}

\begin{document}

\begin{titlepage}
  \begin{center}

    \textsc{\LARGE IT202 - Projet de Système d'Exploitation}\\[2cm]
    \textsc{\large Rapport Intermédiaire}\\[3cm]
    Maxime \textsc{Bellier} \ \ \ Louis \textsc{Boucherie} \ \ \ Jean-Michaël \textsc{Celerier}\\
    Julien \textsc{Chaumont} \ \ \ Bazire \textsc{Houssin} \ \ \ Sylvain \textsc{Vaglica}\\[1cm]
    \textsc{Groupe 3}\\[1.5cm]
    \textsc{\large 23/04/2013 }\\[1.5cm]
    \includegraphics[width=8cm]{logo.png}

  \end{center}
  \vspace{3cm}

\end{titlepage}

\clearpage

%commutation de contexte

\section*{Introduction}

Le projet de Système d'Exploitation consiste en la réalisation d'une bibliothèque de threads. Les tests ayant déjà été implémentés et fixés en amont, il s'agit d'un développement par les tests. Ce premier rapport présentera le travail réalisé à l'issu des trois premières semaines, ainsi que les objectifs attendus d'ici la fin du projet.
%objectifs

\section{Définition des structures de données}

L'une des premières étapes aura été de définir les structures de données à adopter à partir des résultats attendus et de l'implémentation des tests. Cette première partie décrira de manière détaillée les structures choisies.

\subsection{Le type \texttt{thread\_t}}

Le type \texttt{thread\_t} est en fait à la base de notre implémentation: cette structure représente un thread en mémoire. Sa définition est donnée en figure \ref{threadt}.

\begin{figure}[H]
\begin{lstlisting}
typedef enum {READY, SLEEPING, DEAD} STATE;

typedef struct thread_t_
{
  STATE state;
  ucontext_t context;
  void *retval;
  int valgrind_stackid;
  TAILQ_ENTRY(thread_t_) entries;
} *thread_t;
\end{lstlisting}
\caption{Implémentation de \texttt{thread\_t}}
\label{threadt}
\end{figure}

Ses attributs ont chacun leur utilité:
\begin{itemize}
  \item \texttt{state}: état du thread, à savoir \emph{prêt à l'exécution}, \emph{endormi}, ou \emph{mort};
  \item \texttt{context}: contexte d'exécution du thread, géré à l'aide des fonctions de la bibliothèque standard \texttt{getcontext}, \texttt{setcontext}, \texttt{makecontext} et \texttt{swapcontext}, déclarées dans \texttt{ucontext.h};
  \item \texttt{retval}: pointeur vers la valeur de retour de la fonction exécutée dans le thread;
  \item \texttt{valgrind\_stackid}: permet à l'utilitaire \textit{Valgrind} de mieux gérer la détection de problèmes de mémoire dans les piles;
  \item \texttt{entries}: structure contenant des pointeurs vers les threads suivant et précédent. Il s'agit en fait d'une liste doublement chaînée utilisant l'implémentation de \textit{Queue BSD}\footnote{http://linux.die.net/include/sys/queue.h}.
\end{itemize}

\subsection{Le type \texttt{Threads}}

Le type \texttt{Threads} a été mis en place afin de gérer différents threads au cours de l'exécution d'un programme. Il s'agit en fait d'une file contenant les différents threads créés par le programmeur, ce qui permet de passer aisément d'un thread à un autre.

Comme évoqué précédemment, c'est l'implémentation de \textit{Queue BSD} qui est utilisée ici. Cette structure de file assure le passage d'un thread vers le thread suivant ou précédent en temps constant (situation d'un changement de contexte \textit{``naturel''}). La définition du type \texttt{Threads} est donnée en figure \ref{threadst}.

\begin{figure}[H]
\begin{lstlisting}
typedef struct Threads
{
  int is_initialized;
  thread_t main_thread;
  thread_t current_thread;
  TAILQ_HEAD(, thread_t_) list;
  TAILQ_HEAD(, thread_t_) list_sleeping;
  TAILQ_HEAD(, thread_t_) list_dead;
} Threads;
\end{lstlisting}
\caption{Implémentation du type \texttt{Threads}}
\label{threadst}
\end{figure}

Le rôle de chaque attribut est le suivant:
\begin{itemize}
  \item \texttt{is\_initialized}: booléen indiquant si la liste a déjà été initialisée par la création d'un premier thread ou non;
  \item \texttt{main\_thread}: thread correspondant au contexte principal du programme (celui ayant été créé lors de l'initialisation);
  \item \texttt{current\_thread}: thread en train d'être exécuté;
  \item \texttt{list}: liste des threads prêts à être exécutés;
  \item \texttt{list\_sleeping}: liste des threads endormis;
  \item \texttt{list\_dead}: liste des threads morts.
\end{itemize}

\subsection{Fonctionnement}

L'initialisation des structures de données a lieu lors du premier appel à l'une des fonctions de la bibliothèque. Pour plus de facilité, la structure \texttt{Threads} utilisée est en fait définie de manière statique avec une portée globale.

\subsubsection*{L'initialisation}

L'initialisation de \texttt{Threads} consiste simplement en la création des différentes listes en attribut, ainsi qu'en l'initialisation d'un premier thread correspondant au contexte d'appel. Ce thread sera défini comme étant le thread principal.

De plus, l'instruction suivante:
\begin{center}
\verb[atexit(threads_destroy);[
\end{center}
assure la libération mémoire de l'intégralité des allocations dynamiques effectuées à la fin du programme.

\subsubsection*{Création d'un thread}

La création d'un thread se résume en l'allocation dynamique d'une variable \texttt{thread\_t} puis en son initialisation. Il ne reste ensuite qu'à l'insérer à la fin de la liste des threads prêts de la structure \texttt{Threads}.

\subsubsection*{Passage de main}

Le passage de main, à l'aide de la fonction \texttt{thread\_yield}, consiste simplement à placer le thread courant en fin de liste et d'exécuter le thread se trouvant en début de liste. Dans le cas où cette liste serait vide, il faut réveiller un thread endormi pour l'exécuter. Cette fonction se charge d'effectuer le changement de contexte, ce qui lance l'exécution de la fonction associée au thread.

\subsubsection*{Attente de thread}

L'attente d'un thread consiste en fait à attendre qu'il passe à l'état \textit{mort}. Si jamais le thread concerné n'est pas le thread courant, le remplacement est effectué, suivi par le changement de contexte, afin de reprendre son exécution. S'il est endormi, il faut alors le réveiller, le placer dans la liste des threads prêts, et l'exécuter. La valeur de retour du thread est récupérée directement depuis l'attribut \texttt{retval} de la structure \texttt{thread\_t}.

\subsubsection*{Terminer un thread}

Lorsque l'utilisateur demande à terminer un thread, il est simplement indiqué comme mort et placé dans la liste des threads morts. Il ne reste alors qu'à demander à passer la main.


\section{L'avancement actuel du projet}

\subsection{Implémentation}

L'ensemble des fonctions figurant dans le fichier \textit{thread.h} a été implémenté. Les tests pré-existants ont permis de vérifier au fur et à mesure du développement que le code en cours d'écriture était en adéquation avec les prérequis.

\subsection{Tests prédéfinis}


A l'heure actuelle, la totalité des tests ayant été définis au préalable passent avec succès. Mieux encore: la bibliothèque créée pour le projet dépasse la bibliothèque \textit{pthread} sur le test de calcul du $n$\up{ième} élément de la suite de Fibonacci! En effet, le calcul s'effectue sans problème jusqu'au $22$\up{ième} terme; alors qu'en utilisant \textit{pthread}, le temps d'exécution du programme s'envole dès le $13$\up{ième} terme .

\subsection{Tests complémentaires}
Des tests non prévus par le sujet ont également été faits. Ces tests ont été choisis pour le grand nombre de threads qu'ils créent.

Le premier est ``le voyageur de commerce'', qui consiste à trouver le plus court chemin passant par un certain nombre de points. Ce programme crée autant de processus qu'il y a de points. %Nous avons pu l'exécuter avec $nb$ villes en utilisant nos threads et $nb2$ en utilisant \textit{pthread}.

Le second test calcule la somme des éléments d'un tableau. Chaque thread calcule  la somme partielle sur une partie du tableau. La taille du tableau étant fixée, le nombre de threads à utiliser est passé en paramètre (et doit être une puissance de deux). Avec notre implémentation des threads, ce nombre peut monter jusqu'à 1024 threads alors qu'en utilisant la bibliothèque \textit{pthreads}, la limite tombe à 256.

\subsection{Valgrind}

Les tests précédemment évoqués ont également été lancés sous la supervision du logiciel \textit{Valgrind}. Comme attendu, la bibliothèque de thread créée n'est source d'aucune fuite mémoire.

\subsection{Priorités des threads}

En plus des objectifs minimaux des premières séances, un premier essai sur la gestion des priorités a été intégrée au projet. Dans la structure \textit{thread\_t}, deux attributs ont été ajoutés : \texttt{int default\_priority} et \texttt{int current\_priority}. La structure \textit{Threads} a elle aussi un attribut supplémentaire: \textit{int max\_priority}, qui contient la priorité maximale des threads qui sont présents dans la file.

La gestion des priorités est conçue de la manière suivante: lors de la création du thread, une priorité par défaut lui est attribuée. L'utilisateur peut modifier la priorité d'un thread par un appel à la fonction \texttt{set\_thread\_priority} (cette fonction a été faite pour éviter de modifier le prototype des fonctions déjà existantes et utilisées par les tests).

Lors d'un \textit{yields}, la priorité courante du thread est décrémentée. Si un thread a une priorité négative ou nulle, il n'est pas lancé et sa priorité est tout de même décrémentée. Lorsque tous les threads ont une priorité inférieure ou égale à zéro, la priorité de chaque thread est remise à sa valeur initiale ; et la boucle recommence. Ainsi, les threads ayant une priorité haute seront appelés un plus grand nombre de fois (proportionellement à leur priorité).\\

Deux tests ont été implémentés. Le premier, \texttt{17-priority}, vérifie que le nombre d'appels de chaque thread, sur un nombre fixé de \textit{yields}, est proportionnel à sa priorité. Voici le résultat obtenu pour 5 threads :
\begin{verbatim}
 * * * Testing '17-priority' * * *
Thread priority:     | 3   | 3   | 1   | 3   | 5   |
Nb calls per thread: | 299 | 299 | 100 | 299 | 499 |
\end{verbatim}

Le second test, \texttt{18-priority-exit} vérifie en plus l'intégrité de la file de threads lors de la suppression d'un thread de la liste (par un appel à \texttt{thread\_exit} par exemple). De la même manière, on lance une boucle faisant des \textit{yields}. Cette fois, un thread prend fin lorsqu'il a été appelé un certain nombre de fois (fixé au départ). Lorsqu'un thread s'arrète, on affiche le numéro de l'itération courante. La sortie suivante montre le résultat du test pour 5 threads. Les threads à forte priorité s’arrêtent bien avant ceux dont la priorité est plus faible, ce qui est le résultat attendu puisque les threads prioritaire reprennent la main plus souvent.
\begin{verbatim}
 * * * Testing '18-priority-exit' * * *
Thread 1 ended at 347th loop (priority 4)
  Priority-Nb calls:  4-100   1-25   3-74   2-49   4-99  
Thread 5 ended at 350th loop (priority 4)
  Priority-Nb calls:  4-100   1-25   3-75   2-50   4-100  
Thread 3 ended at 400th loop (priority 3)
  Priority-Nb calls:  4-100   1-34   3-100   2-66   4-100  
Thread 4 ended at 450th loop (priority 2)
  Priority-Nb calls:  4-100   1-50   3-100   2-100   4-100  
Thread 2 ended at 500th loop (priority 1)
  Priority-Nb calls:  4-100   1-100   3-100   2-100   4-100
\end{verbatim}

Néanmoins, ce système de priorités est loin d'être exempt de défauts. En effet, cette méthode s'applique très mal par exemple dans le cas où un thread a une priorité très importante, et tous les autres ont la priorité la plus faible: au moment du \textit{yield}, l'algorithme mis en place fera très fréquemment le tour complet de la file avant de finalement redonner la main au thread qu'il venait de quitter.


\section{Nos objectifs pour la suite du projet}

Actuellement, l'équipe s'oriente sur le fait de rendre le projet compatible avec les architectures multic\oe urs. En parallèle, de nouveaux tests sont créés pour vérifier l'intégrité du code source. La gestion des priorités devrait également \^etre améliorée en se basant non pas sur le nombre d'appels, mais sur le temps d'exécution. Cette nouvelle méthode devrait se baser sans trop de problèmes sur l'implémentation de la technique existante, mais nécessitera d'abord la mise en place de la préemption.

Les autres objectifs secondaires n'ont pour le moment pas été choisis et dépendront principalement de l'avancement et de la réussite des travaux actuellement en cours.

\end{document}
